package Hot100;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2022-01-12 17:34
 */
public class canPartition416 {
    /**
     * 416. 分割等和子集
     * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     * 思路：相当于在nums中找到和为所有元素和一半的子集
     * 背包问题，背包容量为所有元素和的一般，0-1背包
     * dp[i][j]表示前i个元素中，背包容量为j，是否可以将背包装满。
     * dp[i][j] = dp[i - 1][j];背包容量不足，不能装入第 i 个物品
     * dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];背包容量够，选择装入或不装入背包
     * */
    public boolean canPartition(int[] nums) {
        int sum= Arrays.stream(nums).sum();
        if(sum%2!=0){
            return false;
        }
        int w=sum/2;
        int n=nums.length;
        boolean[][] dp=new boolean[n+1][w+1];
        for (int i = 0; i <= n; i++) {
            dp[i][0]=true;
        }
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= w ; j++) {
                if (j-nums[i-1]<0){
                    //元素下标后移,背包容量不足，不能装入第 i 个物品
                    dp[i][j]=dp[i-1][j];
                }else {
                    //背包容量够，选择装入或不装入背包
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][w];
    }
}
